/*
 * @lc app=leetcode.cn id=397 lang=typescript
 *
 * [397] 整数替换
 */

// @lc code=start
function integerReplacement(n: number): number {
  // 记忆化搜索
  const hash = new Map<number, number>();
  // 深度优先搜索
  const dfs = (n: number): number => {
    if (n === 1) return 0;
    if (!hash.has(n)) {
      if (n % 2 === 0) {
        hash.set(n, 1 + dfs(n / 2));
      } else {
        // 取最小值
        hash.set(n, 1 + Math.min(dfs(n - 1), dfs(n + 1)));
      }
    }
    return hash.get(n);
  };

  return dfs(n);
}
// @lc code=end
